package com.github.yangyishe.p200;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 128. 最长连续序列
 * https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-interview-150
 * todo 效率待优化,且逻辑略复杂;
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * 示例 2：
 *
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 */
public class Problem128 {
    public static void main(String[] args) {
        int[] nums=new int[]{100,4,200,1,3,2};

        Problem128 problem128 = new Problem128();
        int i = problem128.longestConsecutive(nums);
        System.out.println(i);
    }

    public int longestConsecutive2(int[] nums){

        return 0;
    }

    /**
     * 思路1:
     *
     * 1. 创建一个类, 记录连续数值范围
     * 2. 创建2个哈希表, 键为数字(分别是连续数对象的首值和尾值), 值是该对象(的引用)
     * 3. 每遍历一个数字, 从哈希表中寻找该对象, 寻找原则是查找该数字+1或-1后有没有对应的对象
     * 3.1 如果有且仅有一个, 则直接使用该对象, 并维护该对象即可(每次维护对象的首值或尾值, 同样需要维护哈希表)
     * 3.2 如果有且有两个(只可能是一头一尾), 则将两个对象合并. 合并方法是将其中靠前一个对象的尾部维护为第二个对象的尾部, 再在哈希表中删除第二个对象的维护数据
     * 3.3 如果没有, 则创建一个新的连续数值对象, 并开始维护
     * 4. 最后遍历任意哈希表的值, 获取最大长度即可
     *
     *
     *
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        if (nums.length==0) {
            return 0;
        }
        MyRangeHash myRangeHash = new MyRangeHash();
        for(int num:nums){
            if (myRangeHash.set.contains(num)) {
                continue;
            }else{
                myRangeHash.set.add(num);
            }
            MyRangeObj next = myRangeHash.headMap.get(num + 1);
            MyRangeObj prev = myRangeHash.tailMap.get(num - 1);
            if(next==null&&prev==null){
                myRangeHash.createNew(num);
            }else if(next!=null&&prev!=null){
                myRangeHash.merge(prev,next);
            }else if(next!=null){
                myRangeHash.updateHead(next);
            }else{
                myRangeHash.updateTail(prev);
            }

        }
        int maxLen=0;
        for (MyRangeObj obj : myRangeHash.headMap.values()) {
            maxLen=Math.max(maxLen,obj.length());
        }

        return maxLen;
    }

}

class MyRangeHash{
    // 是否已存在的数字.已存在则无视
    Set<Integer> set=new HashSet<>();
    // 表示维护前下标索引的map
    Map<Integer,MyRangeObj> headMap =new HashMap<>();
    // 表示维护尾下标索引的map
    Map<Integer,MyRangeObj> tailMap =new HashMap<>();

    public void createNew(int num){
        MyRangeObj myRangeObj = new MyRangeObj(num);
        headMap.put(num,myRangeObj);
        tailMap.put(num,myRangeObj);
    }

    public void updateHead(MyRangeObj head){
        headMap.remove(head.startNum);
        head.startNum--;
        headMap.put(head.startNum,head);
    }

    public void updateTail(MyRangeObj tail){
        tailMap.remove(tail.endNum);
        tail.endNum++;
        tailMap.put(tail.endNum,tail);
    }

    public void merge(MyRangeObj prev,MyRangeObj next){
        tailMap.remove(prev.endNum);
        prev.endNum=next.endNum;
        tailMap.put(prev.endNum,prev);

        headMap.remove(next.startNum);

    }
}

class MyRangeObj{
    int startNum;
    int endNum;

    public MyRangeObj(int num) {
        this.startNum = num;
        this.endNum =num;
    }

    public int length(){
        return this.endNum -this.startNum +1;
    }
}
